package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

import data_structure.BTNode;

public class LeetCode_day16 {
	

	/**
	 * Given a triangle, find the minimum path sum from top to bottom. 
	 * Each step you may move to adjacent numbers on the row below.
	 * For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
	 * The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
	 * Note:
	 * Bonus point if you are able to do this using only O(n) extra space, 
	 * where n is the total number of rows in the triangle.
	 * @param triangle
	 */
	
	public static void triangle(int[][] triangle, int preStep, int[] minimum, int step, int sum){
		if(triangle == null) return;
		if(step >= triangle.length) {
			if(sum < minimum[0]) minimum[0] = sum;
			return;
		}
		
		int newSum = sum + triangle[step][preStep];
		if(newSum < minimum[0]) 
			triangle(triangle, preStep, minimum, step+1, newSum);
		
		newSum = sum + triangle[step][preStep+1];
		if(newSum < minimum[0])
			triangle(triangle, preStep+1, minimum, step+1, newSum);
		
		
	}
	
	/**
	 * Say you have an array for which the ith element 
	 * is the price of a given stock on day i.
	 * If you were only permitted to complete at most one transaction 
	 * (ie, buy one and sell one share of the stock), 
	 * design an algorithm to find the maximum profit.
	 * @param price
	 */
	public static void bestTimeToBuyAndSellStock(double[] price){
		if(price == null) return;
		double maxProfit = Integer.MIN_VALUE;
		int start = 0, end = 0;
		
		for(int s = 0 ; s < price.length ; s++){
			double profit = price[s];
			if(profit > maxProfit){
				maxProfit = profit;
				start = s; end = s;
			}
			for(int e = s + 1; e < price.length ; e++){
				profit += price[e];
				if(profit > maxProfit){
					maxProfit = profit;
					start = s; end = e;
				}
			}
		}
		
		System.out.println();
		System.out.println("Max Profit is: "+ maxProfit +" with (" + start + "," + end + ")");
		System.out.println();
	}
	
	/**
	 * ! Say you have an array for which the ith element 
	 * is the price of a given stock on day i.
	 * Design an algorithm to find the maximum profit. 
	 * You may complete as many transactions as you like 
	 * (ie, buy one and sell one share of the stock multiple times). 
	 * However, you may not engage in multiple transactions at the same time 
	 * (ie, you must sell the stock before you buy again).
	 * 
	 * Analysis:
	 * Just find all positive blocks
	 * @param price
	 */
	public static void bestTimeToBuyAndSellStockII(double[] price){
		if(price == null) return;
		double maxProfit = 0.0;
		for(int i = 0 ; i < price.length ; i++){
			if(price[i] > 0) maxProfit += price[i];
		}
		
		System.out.println();
		System.out.println("Max Profit is: "+ maxProfit);
		System.out.println();
	}
	
	/**
	 * ! Say you have an array for which the ith element is the price of a given stock on day i.
	 * Design an algorithm to find the maximum profit. You may complete at most two transactions.
	 * Note:
	 * You may not engage in multiple transactions at the same time 
	 * (ie, you must sell the stock before you buy again).
	 * @param price
	 */
	public static void bestTimeToBuyAndSellStockIII(double[] price){
		if(price == null) return;
		//single transaction
		double maxProfit = Integer.MIN_VALUE;
		
		for(int s = 0 ; s < price.length ; s++){
			double profit = price[s];
			if(profit > maxProfit)
				maxProfit = profit;
			for(int e = s + 1; e < price.length ; e++){
				profit += price[e];
				if(profit > maxProfit)
					maxProfit = profit;
			}
		}
		
		//double transaction
		int start1 = 0, start2 = -1, end1 = -1 , end2 = price.length-1;
		//double maxProfit1 = price[0], maxProfit2 = price[];
		int ind1 = start1, ind2 = end2;
		
		while(ind1 < ind2){
			
		}
		
 		
	}
	
	/**
	 * Given a string, determine if it is a palindrome, 
	 * considering only alphanumeric characters and ignoring cases.
	 * For example,
	 * "A man, a plan, a canal: Panama" is a palindrome.
	 * "race a car" is not a palindrome.
	 * @param s
	 */
	public static void validPalindrome(String s){
		if(s == null) return;
		s = s.toLowerCase();
		s = s.replaceAll("[^a-z]", "");
		int i = 0 , j = s.length()-1;
		while(i <= j){
			if(s.charAt(i++) != s.charAt(j--)){
				System.out.println(false);
				return;
			}
		}
		System.out.println(true);
	}
	
	/**
	 * Given two words (start and end), and a dictionary, 
	 * find the length of shortest transformation sequence from start to end, such that:
	 * Only one letter can be changed at a time
	 * Each intermediate word must exist in the dictionary
	 * For example,
	 * Given:
	 * start = "hit"
	 * end = "cog"
	 * dict = ["hot","dot","dog","lot","log"]
	 * As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
	 * return its length 5.
	 * Note:
	 * Return 0 if there is no such transformation sequence.
	 * All words have the same length.
	 * All words contain only lowercase alphabetic characters.
	 * @param start
	 * @param end
	 * @param dic
	 */
	public static void wordLadder(String start, String end, String[] dic){
		if(start == null || end == null || dic == null) return;
		List<Integer>[] graph = new ArrayList[dic.length];
		for(int i = 0 ; i < graph.length ; i++) graph[i] = new ArrayList<Integer>();
		
		for(int i = 0 ; i < dic.length ; i++)
			for(int j = i ; j < dic.length ; j++){
				int diffNum = 0; boolean flag = true;
				for(int k = 0 ; k < start.length() ; k++){
					if(dic[i].charAt(k) != dic[j].charAt(k)) diffNum++;
					if(diffNum >= 2) {
						flag = false;
						break;
					}
				}
				if(flag){//adjacent
					graph[i].add(j);
					graph[j].add(i);
				}
			}
		//find path
		int inds = 0, inde = 0;
		while(inds < dic.length){
			if(dic[inds].equals(start)) break;
			inds++;
		}
		
		while(inde < dic.length){
			if(dic[inde].equals(end)) break;
			inde++;
		}
		
		if(inds >= dic.length || inde >= dic.length) return;
		
		System.out.println("Steps number is: " + bfsGraphWordLadder(graph, inds, inde));		
	}
	
	private static int bfsGraphWordLadder(List<Integer>[] graph, int inds, int inde){
		boolean[] visited = new boolean[graph.length];
		Queue<Integer> q = new LinkedList<Integer>();
		visited[inds] = true;
		q.offer(inds);
		q.offer(-1);
		List<List<Integer>> pathes = new ArrayList<List<Integer>>();
		int step = 0;
		while(!q.isEmpty()){
			int v = q.poll();
			if(v == -1){
				step++;
				if(!q.isEmpty()) q.offer(-1);
				continue;
			}else if(v == inde) {
				step++;
				return step;
			}
			else{
				for(Integer k : graph[v])//add all adjacent vertices
					if(!visited[k]){
						q.offer(k);
						visited[k] = true;
					}
			}
		}
		return 0;
	}
	
	/**
	 * ! Given two words (start and end), and a dictionary, find all shortest transformation sequences
	 * ! BFS with backtracking.
	 * @param start
	 * @param end
	 * @param dict
	 * @return
	 */
	public static ArrayList<ArrayList<String>> wordLadderII(String start, String end, HashSet<String> dict){
		//build the graph
        dict.add(start); dict.add(end);
        String[] list = dict.toArray(new String[dict.size()]);
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        ArrayList<ArrayList<Short>> ress = new ArrayList<ArrayList<Short>>();
        
        List<Short>[] graph = new ArrayList[list.length];
        for(List<Short> l : graph)
            l = new ArrayList<Short>();
        
        for(short i = 0 ; i < list.length ; i++)
            for(short j = (short) (i+1) ; j < list.length ; j++){
                int diffNum = 0;
                for(short k = 0 ; k < start.length() ; k++){
                    if(list[i].charAt(k) != list[j].charAt(k))
                        diffNum++;
                    if(diffNum >= 2) break;
                }
                if(diffNum == 1){
                    graph[i].add(j);
                    graph[j].add(i);
                }
            }
        
        int inds = 0, inde = 0;
        while(inds < list.length){
        	if(list[inds].equals(start)) break;
			inds++;
		}
		
		while(inde < list.length){
			if(list[inde].equals(end)) break;
			inde++;
		}
		
		List<Integer>[] pre = new ArrayList[graph.length];
		for(List<Integer> l : pre) l = new ArrayList<Integer>();
		Queue<Integer> q = new LinkedList<Integer>();
		int[] distance = new int[graph.length];
		for(int i : graph[inds]){
			q.offer(i);
			pre[i].add(inds);
			distance[i] = 1;
		}
		
		while(!q.isEmpty()){
			int v = q.poll();
			if(v == inde) break;
			int d = distance[v]+1;
			for(int i : graph[v]){
				if(pre[i].size() == 0){
					pre[i].add(v);
					distance[i] = d;
					q.offer(i);
				}else if(distance[i] == d)
					pre[i].add(v);
			}
		}
			
		
		return null;
	}
	
	/**
	 * ! Given an unsorted array of integers, 
	 * find the length of the longest consecutive elements sequence.
	 * For example,
	 * Given [100, 4, 200, 1, 3, 2],
	 * The longest consecutive elements sequence is [1, 2, 3, 4]. 
	 * Return its length: 4.
	 * Your algorithm should run in O(n) complexity.
	 * @param a
	 * @return
	 */
	public static int longestConsecutiveSequence(int[] a){
		if(a == null) return -1;
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int max = 1;
		for(int i : a){
			if(map.containsKey(i)) continue;
			map.put(i, 1);
			if(map.containsKey(i-1)) max = Math.max(max, merge(map,i-1,i));
			if(map.containsKey(i+1)) max = Math.max(max, merge(map,i,i+1));
		}
		return max;
	}
	
	private static int merge(HashMap<Integer, Integer> map, int left, int right){
		int up = right+map.get(right)-1;
		int lower = left-map.get(left)+1;
		int len = up-lower+1;
		map.put(up, len);
		map.put(lower,len);
		return len;
	}
	
	/**
	 * Use the union set
	 * @param a
	 * @return
	 */
	public static int longestConsecutiveSequence1(int[] a){
		HashMap<Integer, Integer> s = new HashMap<Integer, Integer>();
		for(int i : a) s.put(i,-1);
		
		int max = 0;
		for(int i = 0 ; i < a.length ; i++){
			//merge
			if(s.containsKey(a[i]-1)){
				int root1 = s.get(a[i]);
				if(root1 > 0){
					while(s.get(root1) > 0) 
						root1 = s.get(root1);
				}else root1 = a[i];
				
				int root2 = s.get(a[i]-1);
				if(root2 > 0){
					while(s.get(root2) > 0) root2 = s.get(root2);
				}else root2 = a[i]-1;
				if(root1 != root2){
					int sum = s.get(root1) + s.get(root2);
					if(sum < max) max = sum;
					s.put(root1, sum);
					s.put(root2, root1);
				}
			}
			if(s.containsKey(a[i]+1)){
				int root1 = s.get(a[i]);
				if(root1 > 0){
					while(s.get(root1) > 0) root1 = s.get(root1);
				}else root1 = a[i];
				
				int root2 = s.get(a[i]+1);
				if(root2 > 0){
					while(s.get(root2) > 0) root2 = s.get(root2);
				}else root2 = a[i]+1;
				if(root1 != root2){//notice
					int sum = s.get(root1) + s.get(root2);
					if(sum < max) max = sum;
					s.put(root1, sum);
					s.put(root2, root1);
				}
			}
		}
		return -max;
	}
	
	/**
	 * ! Given a binary tree containing digits from 0-9 only, 
	 * each root-to-leaf path could represent a number.
	 * An example is the root-to-leaf path 1->2->3 which represents the number 123.
	 * Find the total sum of all root-to-leaf numbers.
	 * For example,
    1
   / \
  2   3
	 * The root-to-leaf path 1->2 represents the number 12.
	 * The root-to-leaf path 1->3 represents the number 13.
	 * Return the sum = 12 + 13 = 25.
	 * @param root
	 * @return
	 */
	public static int sumRootToLeafNumbers(BTNode<Integer> root){
		if(root == null) return -1;
		//find all numbers, do a post-order traversal root->left->right
		List<String> numbers = postOrder(root);
		int sum = 0;
		for(String s : numbers)
			sum += Integer.valueOf(s);
		System.out.println("\nSum is: "+sum);
		return sum;
	}
	
	private static List<String> postOrder(BTNode<Integer> root){
		if(root == null) return null;
		List<String> list1 = postOrder(root.left);
		List<String> list2 = postOrder(root.right);
		List<String> list = new ArrayList<String>();
		
		if(list1 != null){
			for(String i : list1){
				if(!root.val.toString().equals("0"))
					list.add(root.val + i );
			}
		}
		if(list2 != null){
			for(String i : list2){
				if(!root.val.toString().equals("0"))
					list.add(root.val + i );
			}
		}
		
		if(list.isEmpty()) list.add(root.val.toString());
		return list;
	}
	
	
	public static void surroundedRegions(char[][] board){
		if(board == null) return;
		
		int m = board.length , n = board[0].length;
		ArrayList<Integer> s = new ArrayList<Integer>();
		Set<Integer> visited = new HashSet<Integer>();
		
		for(int i = 0 ; i < m ; i++){
			for(int j = 0 ; j < n ; j++){
				if(board[i][j] == 'X' || visited.contains(i*n+j)) continue;
				s.clear();
				boolean flag = true;
				s.add(i*n+j);
				int ind = 0;
				while(flag && ind <= s.size() - 1){
					Integer coor = s.get(ind);
					int x = coor / n; int y = coor % n;
					if(x == 0 || y == 0 || x == m-1 || y == n-1){
						flag = false;
						break;
					}
					//up
					int newcoor = coor-n;
					if(x-1 >= 0 && board[x-1][y] == 'O' && !visited.contains(newcoor)) {
						s.add(newcoor);
						visited.add(newcoor);
					}
					
					//down
					newcoor = coor+n;
					if(x+1 < m && board[x+1][y] == 'O' && !visited.contains(newcoor)){
						s.add(newcoor);
						visited.add(newcoor);
					}
					//left
					newcoor = coor-1;
					if(y-1 >= 0 && board[x][y-1] == 'O' && !visited.contains(newcoor)){
						s.add(newcoor);
						visited.add(newcoor);
					}
					//right
					newcoor = coor+1;
					if(y+1 < n && board[x][y+1] == 'O' && !visited.contains(newcoor)){
						s.add(newcoor);
						visited.add(newcoor);
					}
					
					ind++;
				}
				if(flag){
					for(Integer coor : s)
						board[coor / n][coor % n] = 'X';
				}
			}
		}
		
		System.out.println();
		for(int i = 0 ; i < m ; i++){
			for(int j = 0 ; j < n ; j++)
				System.out.print(board[i][j]+",");
			System.out.println();
		}
		System.out.println();
	}
	/**
	 * Given a string s, partition s such that 
	 * every substring of the partition is a palindrome.
	 * Return all possible palindrome partitioning of s.
	 * For example, given s = "aab",
	 * Return
  [
    ["aa","b"],
    ["a","a","b"]
  ]
  	 * Analysis:
  	 * Use dynamic programming to find all palindromes. O(n^2), space O(n*(n+1)/2)
  	 * and this form a tree
  	 * Use dfs search and backtracking to find all possible partitioning
  	 * it depends on the search space
	 * @param s
	 */
	public static void palindromePartitioning(String s){
		if(s == null) return;
		int dim = s.length();
		boolean[] upperMatrix = new boolean[dim * (dim+1)/2];
		//find all palindromes
		for(int i = 0 ; i < dim ; i++) upperMatrix[getCoor(i,i,dim)] = true;
		for(int i = 0 ; i < dim-1 ; i++)
			if(s.charAt(i) == s.charAt(i+1)) upperMatrix[getCoor(i,i+1,dim)] = true;
		
		for(int len = 3 ; len <= dim ; len++){
			for(int start = 0 ; start < dim-len ; start++){
				int end = start + len - 1;
				if(s.charAt(start) == s.charAt(end) && upperMatrix[getCoor(start+1, end-1, dim)]) 
					upperMatrix[getCoor(start,end,dim)]  = true;
			}
		}
		
		HashMap<Integer, List<Integer>> hm = new HashMap<Integer, List<Integer>>();
		for(int i = 0 ; i < dim ; i++)
			for(int j = i; j <dim ; j++)
				if(upperMatrix[getCoor(i,j,dim)])
					if(hm.containsKey(i)) hm.get(i).add(j);
					else{
						List<Integer> list = new ArrayList<Integer>();
						list.add(j);
						hm.put(i, list);
					}
		upperMatrix = null;
		List<List<String>> ress = new ArrayList<List<String>>();
		List<String> list = new ArrayList<String>();
		dfs(s, hm, 0, dim, list, ress);
		for(int i = 0 ; i < ress.size() ; i++){
			for(String j : ress.get(i))
				System.out.print(j+",");
			System.out.println();
		}
		
	}
	
	private static void dfs(String str, HashMap<Integer, List<Integer>> hm, int node, int dim, List<String> path, List<List<String>> ress){
		if(node == dim) {
			ress.add(path);//reach the end
		} else if(node < dim){
			List<Integer> list = hm.get(node);
			for(Integer i : list){
				List<String> newPath = new ArrayList<String>();
				newPath.addAll(path);
				newPath.add(str.substring(node,i+1));
				dfs(str, hm, i+1, dim, newPath, ress);
			}
		}
	}
	private static int getCoor(int i, int j, int dim){
		return i*(2*dim-i+1)/2+j-i;
	}
	/**
	 * Given a string s, partition s such that 
	 * every substring of the partition is a palindrome.
	 * Return the minimum cuts needed for a palindrome partitioning of s.
	 * For example, given s = "aab",
	 * Return 1 since the palindrome partitioning 
	 * ["aa","b"] could be produced using 1 cut.
	 * 
	 * Analysis:
  	 * Use dynamic programming to find all palindromes. O(n^2), space O(n*(n+1)/2) 
  	 * and this forms a tree
  	 * Use bfs search to find the minimum cut
  	 * it depends on the search space
	 * @param s
	 */
	public static void palindromePartitioningII(String s){
		if(s == null) return;
		int dim = s.length();
		boolean[] upperMatrix = new boolean[dim * (dim+1)/2];
		//find all palindromes
		for(int i = 0 ; i < dim ; i++) upperMatrix[getCoor(i,i,dim)] = true;
		for(int i = 0 ; i < dim-1 ; i++)
			if(s.charAt(i) == s.charAt(i+1)) upperMatrix[getCoor(i,i+1,dim)] = true;
		
		for(int len = 3 ; len <= dim ; len++){
			for(int start = 0 ; start < dim-len ; start++){
				int end = start + len - 1;
				if(s.charAt(start) == s.charAt(end) && upperMatrix[getCoor(start+1, end-1, dim)]) 
					upperMatrix[getCoor(start,end,dim)]  = true;
			}
		}
		
		HashMap<Integer, List<Integer>> hm = new HashMap<Integer, List<Integer>>();
		for(int i = 0 ; i < dim ; i++)
			for(int j = i; j <dim ; j++)
				if(upperMatrix[getCoor(i,j,dim)])
					if(hm.containsKey(i)) hm.get(i).add(j);
					else{
						List<Integer> list = new ArrayList<Integer>();
						list.add(j);
						hm.put(i, list);
					}
		upperMatrix = null;
		
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(0);
		q.offer(-1);
		int cut = 0;
		while(!q.isEmpty()){
			Integer node = q.poll();
			if(node == dim) break;
			if(node == -1){
				cut++;
				if(!q.isEmpty()) q.offer(-1);
				continue;
			}
			for(Integer i : hm.get(node)){
				q.offer(i+1);
			}
		}
		
		System.out.println("The minimum cut is: "+ cut);
	}
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] triangle = new int[4][];
		triangle[0] = new int[]{2};
		triangle[1] = new int[]{3,4};
		triangle[2] = new int[]{6,5,7};
		triangle[3] = new int[]{4,1,8,3};
		
		int[] minimum = new int[1];
		minimum[0] = Integer.MAX_VALUE;
		triangle(triangle, 0, minimum, 1, triangle[0][0]);
		System.out.println(minimum[0]);

		double[] price = new double[]{-1,3.0,-2.0,2.0,1.0,-4.0,3.0,5.0};
		bestTimeToBuyAndSellStock(price);
		bestTimeToBuyAndSellStockII(price);
		validPalindrome("A man, a plan, a canal: Panama");
		validPalindrome("race a car");
		wordLadder("hit", "cog", new String[]{"hit","hot","cog","dot","dog","lot","log"});
		System.out.println(longestConsecutiveSequence1(new int[]{200,300,1,3,4,500,2}));
		System.out.println(longestConsecutiveSequence(new int[]{200,300,1,3,4,500,2}));
		
		char[][] board = new char[4][4];
		board[0] = new char[]{'X','X','X','X'};
		board[1] = new char[]{'X','O','O','X'};
		board[2] = new char[]{'X','X','O','X'};
		board[3] = new char[]{'X','O','X','X'};
		surroundedRegions(board);
		palindromePartitioning("aabb");
		palindromePartitioningII("aabb");
	}

}
/**
 * Notice:
 * List<Integer>[] graph = new ArrayList<Integer>[dic.length]; // is wrong
 * List<Integer>[] graph = new ArrayList[dic.length];// is correct
 * 
 * 假設矩陣為nxn，為了計算方便，我們讓陣列索引由1開始，上三角矩陣化為一維陣列，若以列為主，其公式為：
 * loc = i*(2*dim-i+1)/2+j-i;     (i<=j)
 * 下三角矩陣化為一維陣列，若以列為主，其公式為：
 * loc = i（i＋1）/2＋j;           (i>=j)
 */
